package org.xingole.leetcode.dp;

public class KInversePairsArray {

    /**
     * <h2>
     * Approach 1: Dynamic Programming
     * 
     * <p>
     * Let dp[i][j] represent the number of schemes where we use the 
     * permutations of the numbers 1, 2, ... i to form any array of
     * length i, and it exactly contains j pairs of inversions. When
     * performing state transitions, we can consider which number
     * among 1, 2, ..., i is selected for the i-th element.
     * 
     * <p>
     * Suppose we select the number k, then the first i - 1 elements of
     * the array are composed of some permutation of 1, ..., k-1 and
     * k+1, ..., i. The number of inversions in an array can be regarded
     * as the sum of the following two parts:
     * 
     * <ul>
     *      <li>The number of reverse pairs produced by the number k with
     * the first i - 1 element;</li>
     *      <li>The number of inversions generated within the first i - 1
     * elements;</li>
     * </ul>
     * 
     * <p>
     * For the first part, we can calculate that the number k will contribute
     * i - k reverse pairs, that is, k + 1, ..., i each with k
     * generating a reverse pair.
     * 
     * <p>
     * For the second part, we hope it can have j - (i - k) inversions, so that
     * there are a total of j inversions. Since we are concerned with the number
     * of inversions generated <strong>internally</strong> within the first i - 1
     * elements, and the inversions are only related to the relative size of the
     * elements, we can
     * 
     * <ul>
     *      <li>The elements 1, ..., k-1 remain unchanged;
     *      <li>Elements such as k+1, ..., i all decrease by 1, becoming k, ..., i-1;
     * </ul>
     * 
     * <p>
     * Such that among the first i-1 elements, the relative sizes of any two elements do
     * not change. At this point, our goal becomes "for 1, 2, ..., i-1, we hope it can
     * have j-(i-k) reverse pairs", which is the subtask dp[i-1][j-(i-k)] in dynamic
     * programming.
     * 
     * <p>
     * Therefore, we can obtain the state transition equation by enumerating k:
     * 
     *      dp[i][j] = sum(dp[i-1][j-(i-k)]) for k = 1, ..., i
     *               = sum(dp[i-1][j-k])     for k = 0, ..., i-1
     * 
     * The recurrence formula from dp[i][j-1] to dp[i][j] can be obtained:
     *      dp[i][j] = dp[i][j-1] - dp[i-1][j-i] + dp[i-1][j]
     */
    public int kInversePairs(int n, int k) {
        final int MOD = (int) 1e9 + 7;

        // we can optimize the space used in dynamic programming, that is,
        // to alternately perform state transitions using two one-dimensional
        // arrays.
        int[][] dp = new int[2][k + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                int cur = i & 1;
                int prev = cur ^ 1;

                dp[cur][j] = 
                    (j - 1 >= 0 ? dp[cur][j - 1] : 0) - (j - i >= 0 ? dp[prev][j - i] : 0) + dp[prev][j];
                
                if (dp[cur][j] >= MOD) {
                    dp[cur][j] -= MOD;
                } else if (dp[cur][j] < 0) {
                    dp[cur][j] += MOD;
                }
            }
        }

        return dp[n & 1][k];
    }
}
